The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
When data is sent across a communications channel, noise and other distortions of the channel may alter the data by the time the data is received. Various error detection and error correction mechanisms are used to detect and possibly correct such errors. One class of error correcting codes (ECC) is linear block ECCs, which include low-density parity check (LDPC) codes.
An LDPC code is a linear code defined by a parity-check matrix H having a low density and thus a small number of 1s per column. The parity-check matrix H can be represented by a bipartite Tanner graph where each column of H is represented by a transmitted variable node, each row by a check node, and each “1” in H by a graph edge connecting a variable node and a check node corresponding to a column-row location of the “1”. The Tanner graph may additionally have non-transmitted variable nodes. Each check node defines a parity check operation.
When using an LDPC code, user data is divided into blocks of K bits or symbols. Each of the blocks is mapped, or encoded, into a codeword having N bits or symbols, where N is greater than K. A number of redundant bits (referred to as “parity bits”) in a LDPC code is N-K. Redundancy allows for detection and correction of errors. The more redundancy the more errors that can be corrected. LDPC codes may be characterized by a rate calculated by dividing K by N.
User data can be encoded by generating a parity-check matrix H, deriving a generator matrix G based on the parity check matrix H, and then encoding the user data based on the generator matrix G. The parity check matrix H has N columns and M rows. The number of encoded bits is equal to the number of columns N in the parity check matrix H. Each row of the parity check matrix H corresponds to a single parity check and a corresponding parity check equation. As an example, a first row of the parity check matrix H may indicate that for any LDPC codeword a modulo 2 of bits 0, 1 and N−1 of the parity check matrix H is 0. If the number of rows M in the parity check matrix H is equal to N-K, then the parity check matrix H is full rank and the number of parity bits is equal to the number of rows in the parity check matrix. If the number of rows M of a parity check matrix H is greater than N-K, then the parity check matrix H has one or more redundant rows. Redundant rows represent redundant parity checks.
The user data may be multiplied by the generator matrix to provide LDPC codewords. Each bit of an LDPC codeword corresponds to a column of the parity check matrix H. An LDPC codeword can be decoded using an iterative algorithm that passes messages along edges of the corresponding Tanner graph from variable nodes to check nodes and vice-versa until convergence is obtained, or a certain number of iterations is reached.